package LC;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/repeated-dna-sequences/description/
 * All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG".
 * When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
 * Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
 * For example,
 * Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
 * Return:
 * ["AAAAACCCCC", "CCCCCAAAAA"].
 */
public class LC_187_RepeatedDNASequences_HashMap_LinkedList {
    public static void main(String[] args) {
        System.out.println(Solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
    }

    static class Solution {
        static List<String> findRepeatedDnaSequences(String s) {
            List<String> res = new LinkedList<>();
            HashMap<String, Integer> maps = new HashMap<>();
            int length = s.length();
            if (length <= 10)
                return res;
            for (int i = 0; i <= length - 10; i++) {
                String subStr = s.substring(i, i + 10);
                if (maps.containsKey(subStr)) {
                    if (maps.get(subStr) == 1) {
                        maps.replace(subStr, -1);
                        res.add(subStr);
                    }
                } else {
                    maps.put(subStr, 1);
                }
            }
            return res;
        }
    }
}